import bisect
import collections
from typing import List

MAX_INT = 10 ** 5


class Solution:
    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:
        index = collections.defaultdict(list)
        for i, c in enumerate(colors):
            index[c].append(i)

        ans = []
        for i, c in queries:
            i1 = bisect.bisect_left(index[c], i)
            i2 = i1 - 1
            res = MAX_INT
            if i1 < len(index[c]):
                res = min(res, index[c][i1] - i)
            if i2 >= 0:
                res = min(res, i - index[c][i2])
            ans.append(res if res != MAX_INT else -1)

        return ans


if __name__ == "__main__":
    # [3,0,3]
    print(Solution().shortestDistanceColor(colors=[1, 1, 2, 1, 3, 2, 2, 3, 3], queries=[[1, 3], [2, 2], [6, 1]]))

    # [-1]
    print(Solution().shortestDistanceColor(colors=[1, 2], queries=[[0, 3]]))
